package LinkList;



class Iter {
    Node p;
    Node q;
    public Iter(LinkList list) {
        p = list.getHead();

    }

    public boolean hasNext() {
        return p != null;
    }

    public String next() {
        String x = p.getV();
        p = p.getNext();

return x;
    }
}






public class LinkList {
    private Node head;
    private Node p;
//    头节点的作用
    public LinkList(){
        head=null;
    }

    public Iter iterator(){
        return new Iter(this);

    }
    protected  Node getHead(){
        return head;
    }
    //1初始化链表。清空过去值
    public void clearList(){
        head=null;

    }

//2头部加节点
    public void addAtHeader(String x){
        Node n=new Node(x);
//        似有不能直接用
        n.setNext(head);
        head=n;
    }
//    3头部删除节点
    public void removeAtHeader(){
        if (head!=null){
            head=head.getNext();
        }
    }
//        4统计链表节点数量，链表遍历
        public int getCount(){
        Node p=head;
//        用p代替head

        int count=0;
        while (p!=null){
            count=count+1;
            p=p.getNext();
        }
        return count;
    }
//    5查找指定节点
    public boolean search(String x) { Node p = head;
        while (p != null) {
            if (p.getV().equals( x) ) {
                break;
            }
            p = p.getNext();
        }
        if (p==null) {
//            空值判断
            return false;
        } else {
            return true;
        }


    }
    //        6尾部增加节点
    public void addAtTall(String x){
        Node n=new Node(x);
        Node p=head;
        if (head==null){
            head=n;
            return;
//            末尾节点next=null;
            //在尾部加节点的方法
        }
        while (p.getNext()!=null){
            p=p.getNext();
        }

//        删除指定节点x(假设链表中的值不重复 ，删除集合里的数据)
//        步骤1.找到x这个节点，如果没有节点，直接返回，否则同步2
//        步骤2：找到当前节点p的前一个节点引用q,q.next=p.next

    }
    //7删除指定节点X,删除成功返回true,失败返回false
    public boolean remove(String x){
//        查找值为X的节点是否存在，如果存在记录节点的上一个节点的位置
        Node p=head;
        Node q=null;
//        当前节点的上一个节点引用
        while (p!=null){
//            开始节点
            if (p.getV().equals(x))
                break;
            q=p;

            p=p.getNext();
        }
if (p==null){
//    遍历结束所以节点，没有查到X

    return false;

}else {

//    p就是指向X的节点，q就是p的前一个节点
    q.setNext(p.getNext());
    return true;

}


    }
//    按升序插入值为X的节点
//    8按升降序插入节点，以升序为例
//    有序链表，给定一个X按顺序插入X到链表1，3，5，7，9 X=2
//    步骤1找到X对应插入的节点位置，找到刚好大于X的节点p及其前一个节点q

    public void insert(String x){
//        查到值刚好大于X的节点是否存在，如果存在，记录节点的上一个节点位置

       Node p=head;
        Node q=null;
//        X=10,1,2,3,4,5,10
        while (p!=null){
//            开始节点
            if (p.getV().compareTo(x)>0)
                break;
            q=p;

            p=p.getNext();
        }

        if ( q==null&&p==null)
            head = new Node(x);

            if (p == null && q != null)
                q.setNext(new Node(x));

            if (p != null && q == null)
                addAtHeader(x);

            if (p != null && q != null) {
                Node n = new Node(x);
                n.setNext(p);
                q.setNext(n);
            }



    }
}













